home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graphics / line_arrange.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.4 KB  |  120 lines
  1. #include <LEDA/subdivision.h>
  2. #include <LEDA/plane_alg.h>
  3. #include <LEDA/window.h>
  4.  
  5.  
  6.  
  7.  
  8. void  show_face(subdivision<int>& G, face f, window& W)
  9. { list<node> L = G.adj_nodes(f);
  10.   list<point> P;
  11.   node v;
  12.   forall(v,L) P.append(G[v]);
  13.   W.draw_filled_polygon(P,red);
  14. }
  15.  
  16.  
  17. main()
  18. {
  19.  
  20.   window W;
  21.  
  22.   W.init(0,1000,0);
  23.  
  24.   W.message("            Arrangement of line segments                ");
  25.   W.message("                                                        ");
  26.   W.message("This program computes an arrangement of straight lines. ");
  27.   W.message("Use the left button to insert a sequence of lines and ");
  28.   W.message("terminate the input by clicking the right button. Now");
  29.   W.message("you can input query points with the left button. For ");
  30.   W.message("each point p the face of the arrangment containing p ");
  31.   W.message("is computed and displayed. Terminate the program by  "); 
  32.   W.message("pressing the right mouse key.                        ");
  33.   W.message("                                                     ");
  34.   W.message("Click any button to start.                           ");
  35.   W.read_mouse();
  36.   W.clear();
  37.  
  38.  
  39.  
  40.   list<segment> seglist1,seglist2;
  41.  
  42.   // build up a frame
  43.  
  44.   double x0 = W.xmin();
  45.   double x1 = W.xmax();
  46.   double y0 = W.ymin();
  47.   double y1 = W.ymax();
  48.  
  49.   segment b(x0,y0,x1,y0);
  50.   segment t(x0,y1,x1,y1);
  51.   segment l(x0,y0,x0,y1);
  52.   segment r(x1,y0,x1,y1);
  53.  
  54.   seglist1.append(b);
  55.   seglist1.append(t);
  56.   seglist1.append(l);
  57.   seglist1.append(r);
  58.  
  59.   line L;
  60.  
  61.   while ( W >> L ) 
  62.   {  W << L;
  63.      if (L.vertical()) 
  64.         seglist1.append(segment(L.x_proj(y0),y0,L.x_proj(y1),y1));
  65.      else 
  66.         seglist1.append(segment(x0,L.y_proj(x0),x1,L.y_proj(x1)));
  67.    }
  68.  
  69.   W.message("Computing subdivision");
  70.   newline;
  71.  
  72.   GRAPH<point,int> G;
  73.  
  74.   SWEEP_SEGMENTS(seglist1,seglist2,G);
  75.  
  76.  
  77.   // insert reverse edges
  78.  
  79.   edge e;
  80.   list<edge> E = G.all_edges();
  81.   forall(e,E) G.new_edge(target(e),source(e),G[e]);
  82.  
  83.   // sort edges counter-clockwise
  84.  
  85.   edge_array<double> angle(G);
  86.  
  87.   forall_edges(e,G)
  88.   { segment s(G[source(e)],G[target(e)]);
  89.     angle[e] = s.angle();
  90.    }
  91.  
  92.   G.sort_edges(angle);
  93.  
  94.   subdivision<int> S(G);
  95.  
  96.   W.clear(); 
  97.   W.set_line_width(2);
  98.  
  99.   forall_edges(e,G)
  100.   W.draw_segment(G[source(e)], G[target(e)],blue);
  101.  
  102.  
  103.   // Locate points
  104.  
  105.   W.set_mode(xor_mode);
  106.  
  107.   point p;
  108.   face  f=nil;
  109.  
  110.   W.message("Give query points !");
  111.  
  112.   while (W >> p)
  113.   { if (f) show_face(S,f,W);
  114.     f = S.locate_point(p);
  115.     show_face(S,f,W);
  116.    }
  117.  
  118.   return 0;
  119. }
  120.